// https://www.lintcode.com/problem/multi-string-search/

public class Solution {
    /**
     * @param sourceString: a string
     * @param targetStrings: a string array
     * @return: Returns a bool array indicating whether each string in targetStrings is a substring of the sourceString
     */
    public boolean[] whetherStringsAreSubstrings(String sourceString, String[] targetStrings) {
        // write your code here
        boolean[] ret = new boolean[targetStrings.length];
        Arrays.fill(ret, false);
        int srcLen = sourceString.length();
        Map<Character, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < srcLen; ++i) {
            Character c = sourceString.charAt(i);
            if (!map.containsKey(c)) {
                map.put(c, new ArrayList<>());
            }
            map.get(c).add(i);
        }
        for (int i = 0; i < targetStrings.length; ++i) {
            String s = targetStrings[i];
            if (s.length() > 0) {
                Character c = s.charAt(0);
                if (map.containsKey(c)) {
                    for (Integer start : map.get(c)) {
                        boolean r = true;
                        for (int j = 0; j < s.length(); ++j) {
                            if ((start + j) < srcLen) {
                                if (s.charAt(j) != sourceString.charAt(start + j)) {
                                    r = false;
                                    continue;
                                }
                            } else {
                                r = false;
                                continue;
                            }
                        }
                        if (r) {
                            ret[i] = true;
                            break;
                        }
                    }
                }
            } else {
                ret[i] = true;
            }
        }
        return ret;
    }
}